perm filename B07[162,RWF] blob sn#761200 filedate 1984-07-12 generic text, type C, neo UTF8
COMMENT āŠ—   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	Exercise
C00003 ENDMK
CāŠ—;
Exercise

N items are inserted into a binary tree in random order.  When possible, a node
is entered into the same page as its parent.  When a node is entered into a new
page, that page is reserved for the node and its descendants.  Assume a page can
hold  P  nodes.

(1) How many page accesses, on the average, are required to enter the Nā†‘{th} node?

(2) How many page accesses, on the average, are required to enter the first N nodes?

(3) How many pages, on the average, are in use when  N  nodes have been entered?